#include<vector>
#include<iostream>
#include<numeric>
#include<functional>
#include<algorithm>
using namespace std;

namespace leetcode{
    class solution_6073_zkm{
    /*
    @url:    https://leetcode-cn.com/problems/longest-path-with-different-adjacent-characters/
    @method: dfs
    */
    public:
        solution_6073_zkm(){
            vector<int>parent; string s;
            get_data(parent, s);
            cout<<longestPath(parent, s)<<endl;
        }

        void get_data(vector<int>& data, string& str){
            data = {-1,0,0,1,1,2};
            str = "abacbe";
        }

        int longestPath(vector<int>& parent, string s) {
            vector<vector<int>> graph(s.length());
            int sz = parent.size();
            int ans = 0;
            for(int i=1;i<sz;++i){
                graph[parent[i]].push_back(i);
            }
            function<int(int)> dfs = [&](int i)->int{
                int max_len = 0;
                for(int j:graph[i]){
                    int len = dfs(j)+1;
                    if(s[j]!=s[i]){
                        ans = max(ans, len+max_len);
                        max_len = max(len, max_len);
                    }
                }
                return max_len;
            };
            dfs(0);
            return ans+1;
        }
    };
}